\doxysection{Avl\+Tree$<$ Comparable $>$ Class Template Reference}
\label{class_avl_tree}\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}


An Avltree.  




{\ttfamily \#include $<$Binary\+Tree.\+h$>$}



Inheritance diagram for Avl\+Tree$<$ Comparable $>$\+:
\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=550pt]{class_avl_tree__inherit__graph}
\end{center}
\end{figure}


Collaboration diagram for Avl\+Tree$<$ Comparable $>$\+:
\nopagebreak
\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=550pt]{class_avl_tree__coll__graph}
\end{center}
\end{figure}
\doxysubsection*{Classes}
\begin{DoxyCompactItemize}
\item 
struct \textbf{ Avl\+Node}
\begin{DoxyCompactList}\small\item\em Node with height. \end{DoxyCompactList}\end{DoxyCompactItemize}
\doxysubsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
virtual \textbf{ $\sim$\+Avl\+Tree} ()
\item 
virtual void \textbf{ insert} (const Comparable \&x)
\item 
virtual void \textbf{ insert} (Comparable \&\&x)
\item 
virtual void \textbf{ remove} (const Comparable \&x)
\item 
virtual void \textbf{ remove} (Comparable \&\&x)
\item 
const Comparable \& \textbf{ find\+Min} () const
\item 
const Comparable \& \textbf{ find\+Max} () const
\item 
void \textbf{ print\+Tree} (ostream \&out=cout) const
\item 
void \textbf{ make\+Empty} ()
\end{DoxyCompactItemize}
\doxysubsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
void \textbf{ balance} (\textbf{ Avl\+Node} $\ast$\&t)
\item 
void \textbf{ rotate\+With\+Left\+Child} (\textbf{ Avl\+Node} $\ast$\&k2)
\item 
void \textbf{ rotate\+With\+Right\+Child} (\textbf{ Avl\+Node} $\ast$\&k1)
\item 
void \textbf{ double\+With\+Left\+Child} (\textbf{ Avl\+Node} $\ast$\&k3)
\item 
void \textbf{ double\+With\+Right\+Child} (\textbf{ Avl\+Node} $\ast$\&k1)
\end{DoxyCompactItemize}
\doxysubsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\textbf{ Avl\+Node} $\ast$ \textbf{ root} = nullptr
\end{DoxyCompactItemize}
\doxysubsection*{Static Private Attributes}
\begin{DoxyCompactItemize}
\item 
static const int \textbf{ A\+L\+L\+O\+W\+E\+D\+\_\+\+I\+M\+B\+A\+L\+A\+N\+CE} = 1
\end{DoxyCompactItemize}


\doxysubsection{Detailed Description}
\subsubsection*{template$<$typename Comparable$>$\newline
class Avl\+Tree$<$ Comparable $>$}

An Avltree. 


\begin{DoxyTemplParams}{Template Parameters}
{\em Comparable} & \\
\hline
\end{DoxyTemplParams}


\doxysubsection{Constructor \& Destructor Documentation}
\mbox{\label{class_avl_tree_ad518a685acd3c71659d11777649233e4}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!````~AvlTree@{$\sim$AvlTree}}
\index{````~AvlTree@{$\sim$AvlTree}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{$\sim$AvlTree()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
virtual \textbf{ Avl\+Tree}$<$ Comparable $>$\+::$\sim$\textbf{ Avl\+Tree} (\begin{DoxyParamCaption}{ }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [virtual]}}



\doxysubsection{Member Function Documentation}
\mbox{\label{class_avl_tree_a68ab7bcaf7e014d13f7ef693735d1f51}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!balance@{balance}}
\index{balance@{balance}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{balance()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::balance (\begin{DoxyParamCaption}\item[{\textbf{ Avl\+Node} $\ast$\&}]{t }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [private]}}

\mbox{\label{class_avl_tree_a704f818938b6034d133ad409a694ba32}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!doubleWithLeftChild@{doubleWithLeftChild}}
\index{doubleWithLeftChild@{doubleWithLeftChild}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{doubleWithLeftChild()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::double\+With\+Left\+Child (\begin{DoxyParamCaption}\item[{\textbf{ Avl\+Node} $\ast$\&}]{k3 }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [private]}}

Double rotate binary tree node\+: first left child. with its right child; then node k3 with new left child. For A\+VL trees, this is a double rotation for case 2. Update heights, then set new root. \mbox{\label{class_avl_tree_a34aa220c7e759c83faae4744471c1ed2}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!doubleWithRightChild@{doubleWithRightChild}}
\index{doubleWithRightChild@{doubleWithRightChild}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{doubleWithRightChild()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::double\+With\+Right\+Child (\begin{DoxyParamCaption}\item[{\textbf{ Avl\+Node} $\ast$\&}]{k1 }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [private]}}

Double rotate binary tree node\+: first right child. with its left child; then node k1 with new right child. For A\+VL trees, this is a double rotation for case 3. Update heights, then set new root. \mbox{\label{class_bst_tree_a57eb8235cc129e90871524a5c60bc814}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!findMax@{findMax}}
\index{findMax@{findMax}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{findMax()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
const Comparable\& \textbf{ Bst\+Tree}$<$ Comparable $>$\+::find\+Max (\begin{DoxyParamCaption}{ }\end{DoxyParamCaption}) const\hspace{0.3cm}{\ttfamily [inherited]}}

Find the largest item in the tree. Throw Underflow\+Exception if empty. \mbox{\label{class_bst_tree_a4106cfce2da1be70b4b22f1c41e5d406}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!findMin@{findMin}}
\index{findMin@{findMin}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{findMin()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
const Comparable\& \textbf{ Bst\+Tree}$<$ Comparable $>$\+::find\+Min (\begin{DoxyParamCaption}{ }\end{DoxyParamCaption}) const\hspace{0.3cm}{\ttfamily [inherited]}}

Find the smallest item in the tree. \mbox{\label{class_avl_tree_ad9feb22f565e013c60176ab0dc7adba4}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!insert@{insert}}
\index{insert@{insert}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{insert()\hspace{0.1cm}{\footnotesize\ttfamily [1/2]}}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
virtual void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::insert (\begin{DoxyParamCaption}\item[{Comparable \&\&}]{x }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [virtual]}}



Reimplemented from \textbf{ Bst\+Tree$<$ Comparable $>$} \doxyref{}{p.}{class_bst_tree_ad1fd360ecaf13dd46d1b3e4030647af1}.

\mbox{\label{class_avl_tree_aff480dbd38c3803011882dab799871dc}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!insert@{insert}}
\index{insert@{insert}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{insert()\hspace{0.1cm}{\footnotesize\ttfamily [2/2]}}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
virtual void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::insert (\begin{DoxyParamCaption}\item[{const Comparable \&}]{x }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [virtual]}}

Insert x into the tree; duplicates are ignored. 

Reimplemented from \textbf{ Bst\+Tree$<$ Comparable $>$} \doxyref{}{p.}{class_bst_tree_a8c92bedb44279045795259b36031c725}.

\mbox{\label{class_binary_tree_af1cb2a82a7837713d1d0e71cd90a76a0}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!makeEmpty@{makeEmpty}}
\index{makeEmpty@{makeEmpty}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{makeEmpty()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Binary\+Tree}$<$ Comparable $>$\+::make\+Empty (\begin{DoxyParamCaption}{ }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inherited]}}

Make the tree logically empty. \mbox{\label{class_binary_tree_a2ed034626b76cf27efe77bce17604bc4}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!printTree@{printTree}}
\index{printTree@{printTree}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{printTree()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Binary\+Tree}$<$ Comparable $>$\+::print\+Tree (\begin{DoxyParamCaption}\item[{ostream \&}]{out = {\ttfamily cout} }\end{DoxyParamCaption}) const\hspace{0.3cm}{\ttfamily [inherited]}}

Print the tree contents. \mbox{\label{class_avl_tree_ab79e0850047dec805260735bb35d1b51}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!remove@{remove}}
\index{remove@{remove}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{remove()\hspace{0.1cm}{\footnotesize\ttfamily [1/2]}}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
virtual void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::remove (\begin{DoxyParamCaption}\item[{Comparable \&\&}]{x }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [virtual]}}



Reimplemented from \textbf{ Bst\+Tree$<$ Comparable $>$} \doxyref{}{p.}{class_bst_tree_a0251edb51327b40d42e576c885c24334}.

\mbox{\label{class_avl_tree_af87eb93a5639ae6d3661ce1c93680e14}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!remove@{remove}}
\index{remove@{remove}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{remove()\hspace{0.1cm}{\footnotesize\ttfamily [2/2]}}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
virtual void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::remove (\begin{DoxyParamCaption}\item[{const Comparable \&}]{x }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [virtual]}}

Remove x from the tree. Nothing is done if x is not found. 

Reimplemented from \textbf{ Bst\+Tree$<$ Comparable $>$} \doxyref{}{p.}{class_bst_tree_a7cb0b1bd945708ccf9e4af1905b6ac95}.

\mbox{\label{class_avl_tree_acd0214943ec541ee6bd98799c375a495}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!rotateWithLeftChild@{rotateWithLeftChild}}
\index{rotateWithLeftChild@{rotateWithLeftChild}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{rotateWithLeftChild()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::rotate\+With\+Left\+Child (\begin{DoxyParamCaption}\item[{\textbf{ Avl\+Node} $\ast$\&}]{k2 }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [private]}}

Rotate binary tree node with left child. For A\+VL trees, this is a single rotation for case 1. Update heights, then set new root. \mbox{\label{class_avl_tree_a4c9b61185e21b3daf6560a53a86700bc}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!rotateWithRightChild@{rotateWithRightChild}}
\index{rotateWithRightChild@{rotateWithRightChild}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{rotateWithRightChild()}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
void \textbf{ Avl\+Tree}$<$ Comparable $>$\+::rotate\+With\+Right\+Child (\begin{DoxyParamCaption}\item[{\textbf{ Avl\+Node} $\ast$\&}]{k1 }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [private]}}

Rotate binary tree node with right child. For A\+VL trees, this is a single rotation for case 4. Update heights, then set new root. 

\doxysubsection{Member Data Documentation}
\mbox{\label{class_avl_tree_ae5d5973d06b219a4a58d0bc53c75557a}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!ALLOWED\_IMBALANCE@{ALLOWED\_IMBALANCE}}
\index{ALLOWED\_IMBALANCE@{ALLOWED\_IMBALANCE}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{ALLOWED\_IMBALANCE}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
const int \textbf{ Avl\+Tree}$<$ Comparable $>$\+::A\+L\+L\+O\+W\+E\+D\+\_\+\+I\+M\+B\+A\+L\+A\+N\+CE = 1\hspace{0.3cm}{\ttfamily [static]}, {\ttfamily [private]}}

\mbox{\label{class_avl_tree_a520c315e65c1a87a26ede5c72f565cd4}} 
\index{AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}!root@{root}}
\index{root@{root}!AvlTree$<$ Comparable $>$@{AvlTree$<$ Comparable $>$}}
\doxysubsubsection{root}
{\footnotesize\ttfamily template$<$typename Comparable $>$ \\
\textbf{ Avl\+Node}$\ast$ \textbf{ Avl\+Tree}$<$ Comparable $>$\+::root = nullptr\hspace{0.3cm}{\ttfamily [private]}}



The documentation for this class was generated from the following file\+:\begin{DoxyCompactItemize}
\item 
\textbf{ Binary\+Tree.\+h}\end{DoxyCompactItemize}
